package random;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class ASawGridLong  implements ASawGrid {

	private final int size;
	
	private final ArrayMap mapHL;

	private final ArrayMap mapVL;

	private final ArrayMap mapHS;

	private boolean dirHS;

	private final ArrayMap mapVS;

	private boolean dirVS;

	private final int cellSize;

	private final int threshold;

	public ASawGridLong(int cellSize, int size, int threshold) {
		super();
		this.cellSize = cellSize;
		this.size = size;
		this.threshold = threshold;
		this.mapHL = new ArrayMap();
		this.mapVL = new ArrayMap();
		this.mapHS = new ArrayMap();
		this.mapVS = new ArrayMap();
	}

	public final boolean intersectV(final int x, final int y, final int length) {
		final int min = length > 0 ? x + 1 : x + length;
		final int max = length > 0 ? x + length : x - 1;
		{
			final int[] coord = { min / this.cellSize, y / this.cellSize };
			final List<int[]> list = mapVL.get(coord);
			if (list != null) {
				final ListIterator<int[]> it = list.listIterator(list.size());
				while (it.hasPrevious()) {
					int[] i = it.previous();
					if (min <= i[0] && i[0] <= max && i[1] <= y && y <= i[2]) {
						return true;
					}
				}
			}
		}
		if (min / this.cellSize != max / this.cellSize) {
			final int[] coord = { max / this.cellSize, y / this.cellSize };
			final List<int[]> list = mapVL.get(coord);
			if (list != null) {
				final ListIterator<int[]> it = list.listIterator(list.size());
				while (it.hasPrevious()) {
					int[] i = it.previous();
					if (min <= i[0] && i[0] <= max && i[1] <= y && y <= i[2]) {
						return true;
					}
				}
			}
		}
		return false;

	}

	public final boolean intersectH(final int x, final int y, final int length) {
		final int min = length > 0 ? y + 1 : y + length;
		final int max = length > 0 ? y + length : y - 1;
		{
			final int[] coord = { x / this.cellSize, min / this.cellSize };
			final List<int[]> list = mapHL.get(coord);
			if (list != null) {
				final ListIterator<int[]> it = list.listIterator(list.size());
				while (it.hasPrevious()) {
					int[] i = it.previous();
					if (min <= i[0] && i[0] <= max && i[1] <= x && x <= i[2]) {
						return true;
					}
				}
			}
		}
		if (min / this.cellSize != max / this.cellSize) {
			final int[] coord = { x / this.cellSize, max / this.cellSize };
			final List<int[]> list = mapHL.get(coord);
			if (list != null) {
				final ListIterator<int[]> it = list.listIterator(list.size());
				while (it.hasPrevious()) {
					int[] i = it.previous();
					if (min <= i[0] && i[0] <= max && i[1] <= x && x <= i[2]) {
						return true;
					}
				}
			}
		}
		return false;

	}

	public final void addH(final int x, final int y, final int length) {
		final int min = length > 0 ? x : x + length;
		final int max = length > 0 ? x + length : x;
		if (Math.abs(length) > this.threshold) {
			{
				final int[] coord = { min / this.cellSize, y / this.cellSize };
				addHL(y, min, max, coord);
			}
			if (min / this.cellSize != max / this.cellSize) {
				final int[] coord = { max / this.cellSize, y / this.cellSize };
				addHL(y, min, max, coord);
			}
		} else {
			dirHS = length > 0;
			{
				final int[] coord = { min / this.cellSize, y / this.cellSize };
				addHS(y, min, max, coord);
			}
			if (min / this.cellSize != max / this.cellSize) {
				final int[] coord = { max / this.cellSize, y / this.cellSize };
				addHS(y, min, max, coord);
			}
		}
	}

	private final void addHL(final int y, final int min, final int max, final int[] coord) {
		List<int[]> list = mapHL.get(coord);
		if (list == null) {
			list = new LinkedList<int[]>();
			mapHL.put(coord, list);
		}
		{
			final int[] i = { y, min, max };
			if (!dirVS) {
				final ListIterator<int[]> li = list.listIterator();
				while (li.hasNext() && li.next()[0] < y)
					;
				if (li.hasNext()) {
					li.previous();
				}
				li.add(i);
			} else {
				final ListIterator<int[]> li = list.listIterator(list.size());
				while (li.hasPrevious() && li.previous()[0] > y)
					;
				if (li.hasPrevious()) {
					li.next();
				}
				li.add(i);
			}
		}
	}

	private final void addHS(final int y, final int min, final int max, final int[] coord) {
		List<int[]> list = mapHS.get(coord);
		if (list == null) {
			list = new LinkedList<int[]>();
			mapHS.put(coord, list);
		}
		{
			final int[] i = { y, min, max };
			if (!dirHS) {
				final ListIterator<int[]> li = list.listIterator();
				while (li.hasNext() && li.next()[1] < min)
					;
				if (li.hasNext()) {
					li.previous();
				}
				li.add(i);
			} else {
				final ListIterator<int[]> li = list.listIterator(list.size());
				while (li.hasPrevious() && li.previous()[1] > min)
					;
				if (li.hasPrevious()) {
					li.next();
				}
				li.add(i);
			}
		}
	}

	public final void addV(final int x, final int y, final int length) {
		final int min = length > 0 ? y : y + length;
		final int max = length > 0 ? y + length : y;
		if (Math.abs(length) > this.threshold) {
			{
				final int[] coord = { x / this.cellSize, min / this.cellSize };
				addVL(x, min, max, coord);
			}
			if (min / this.cellSize != max / this.cellSize) {
				final int[] coord = { x / this.cellSize, max / this.cellSize };
				addVL(x, min, max, coord);
			}
		} else {
			dirVS = length > 0;
			{
				final int[] coord = { min / this.cellSize, y / this.cellSize };
				addVS(y, min, max, coord);
			}
			if (min / this.cellSize != max / this.cellSize) {
				final int[] coord = { max / this.cellSize, y / this.cellSize };
				addVS(y, min, max, coord);
			}
		}
	}

	private final void addVL(final int x, final int min, final int max, final int[] coord) {
		List<int[]> list = mapVL.get(coord);
		if (list == null) {
			list = new LinkedList<int[]>();
			mapVL.put(coord, list);
		}
		{
			final int[] i = { x, min, max };
			if (!dirHS) {
				final ListIterator<int[]> li = list.listIterator();
				while (li.hasNext() && li.next()[0] < x)
					;
				if (li.hasNext()) {
					li.previous();
				}
				li.add(i);
			} else {
				final ListIterator<int[]> li = list.listIterator(list.size());
				while (li.hasPrevious() && li.previous()[0] > x)
					;
				if (li.hasPrevious()) {
					li.next();
				}
				li.add(i);
			}
		}
	}

	private final void addVS(final int y, final int min, final int max, final int[] coord) {
		List<int[]> list = mapVS.get(coord);
		if (list == null) {
			list = new LinkedList<int[]>();
			mapVS.put(coord, list);
		}
		{
			final int[] i = { y, min, max };
			if (!dirVS) {
				final ListIterator<int[]> li = list.listIterator();
				while (li.hasNext() && li.next()[1] < min)
					;
				if (li.hasNext()) {
					li.previous();
				}
				li.add(i);
			} else {
				final ListIterator<int[]> li = list.listIterator(list.size());
				while (li.hasPrevious() && li.previous()[1] > min)
					;
				if (li.hasPrevious()) {
					li.next();
				}
				li.add(i);
			}
		}
	}

	private final class ArrayMap {

		private final List<int[]>[][] arr = new List[size][];

		private final void put(int[] key, List<int[]> value) {
			final int x = key[0];
			final int y = key[1];
			List<int[]>[] a;
			if ((a = arr[x]) == null) {
				a = arr[x] = new List[size];
			}
			a[y] = value;
			return;
		}

		private final List<int[]> get(int[] key) {
			final int x = key[0];
			final int y = key[1];
			final List<int[]>[] a;
			if ((a = arr[x]) == null) {
				return null;
			}
			return a[y];
		}

	}
}
